package leetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class LC11 {
    public static void main(String[] args) {
        LC11 lc11 = new LC11();
        System.out.println(Arrays.toString(lc11.maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans = new int[nums.length - k + 1];
        Queue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        for (int i = 0; i < k; i++) {
            queue.add(new int[]{nums[i],i});
        }
        ans[0] = queue.peek()[0];
        for (int i = k; i < nums.length; i++) {
            queue.add(new int[]{nums[i],i});
            while(queue.peek()[1] <= i-k){
                queue.poll();
            }
            ans[nums.length-k+1] = queue.peek()[0];
        }
        return ans;
    }
}
